package algorithm;

import java.util.Arrays;

/**
 * @author fangkun
 * @create 2022-05-20-9:10
 *
 * 204 埃氏筛法
 */
public class CountPrimes {

    public static void main(String[] args) {
        int i = countPrimes(10);
        System.out.println(i);
    }

    static int countPrimes(int n) {

        boolean[] isPrime = new boolean[n];

        Arrays.fill(isPrime, true);

        for (int i = 2; i * i < n; i++)

            if (isPrime[i])
                for (int j = i * i; j < n; j += i)
                    isPrime[j] = false;

        int count = 0;
        for (int i = 2; i < n; i++)
            if (isPrime[i]) count++;

        return count;
    }

}
